#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
	int n = nums1.size(), m = nums2.size();
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (nums1[i-1] == nums2[j-1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	return dp[n][m];
}
int numDistinct(string s, string t) {
	int n = s.size(), m = t.size();
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 0; i <= n; i++)
		dp[0][i] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			dp[i][j] = dp[i][j - 1];
			if (s[i - 1] == t[j - 1])
				dp[i][j] += dp[i - 1][j - 1];
		}
	}
	return dp[n][m];
}
vector<bool> row;
vector<bool> col;
vector<bool> grid1;
vector<bool> grid2;
int ret,_n;
void dfs(int depth)
{
	if (depth == _n)
	{
		ret++;
		return;
	}
	for (int y = depth; y < _n; y++)
	{
		for (int x = 0; x < _n; x++)
		{
			if (!col[x]  && !grid1[x + y]
				&& !grid2[(y - x + 2 * _n + 1) % (2 * _n + 1)])
			{
				col[x] = row[y] = true;
				grid1[x + y] = grid2[(y - x + 2 * _n + 1) % (2 * _n + 1)] = true;
				dfs(y+1);
				col[x] = row[y] = false;
				grid1[x + y] = grid2[(y - x + 2 * _n + 1) % (2 * _n + 1)] = false;
			}
			if (row[y] == false)
				return;
		}
	}
}
int totalNQueens(int n) {
	col.resize(n);
	row.resize(n);
	grid1.resize(2 * n + 1), grid2.resize(2 * n + 1);
	_n = n;
	dfs(0);
	return ret;
}
vector<vector<int>> generate(int numRows) {
	vector<vector<int>> ret;
	ret.push_back({ 1 });
	ret.push_back({ 1,1 });
	for (int i = 2; i < numRows; i++)
	{
		vector<int> v;
		v.resize(i + 1);
		v[0] = v[v.size() - 1] = 1;
		for (int j = 1; j < i; j++)
		{
			v[j] = ret[i - 1][j - 1] + ret[i - 1][j];
		}
		ret.push_back(v);
	}
	return ret;
}
int removeDuplicates(vector<int>& nums) {
	vector<int>::iterator it = nums.begin();
	auto pre = it++;
	int count = 1;
	while (it != nums.end())
	{
		if (*it == *pre)
			it = nums.erase(it);
		else
		{
			count++;
			pre = it++;
		}
	}
	return count;
}
vector<int> singleNumber(vector<int>& nums) {
	int tmp = 0;
	for (auto& e : nums)
		tmp ^= e;
	int pos = 0;
	while (tmp % 2 == 0)
	{
		tmp=tmp >> 1;
		pos++;
	}
	int count1 = 0, count2 = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[i] >> pos % 2 == 0)
			count1 ^= nums[i];
		else
			count2 ^= nums[i];
	}
	return { count1,count2 };
}
int main()
{
	generate(4);
	return 0;
}